package cn.edu.jxau.test;

/**
 * 判断图是否存在环（假设不存在自环或平行边）
 * @author 付大石
 */
public class Cycle {

    public static void main(String[] args) {

        UndirectedGraph g = new UndirectedGraph(3);
        g.addEdge(0,1);
        g.addEdge(1,2);
        g.addEdge(2,0);
//        g.addEdge(2,0);
        Cycle c = new Cycle(g);
        System.out.println(c.hasCycle);
    }

    private boolean[] marked;
    private boolean hasCycle;

    public Cycle(Graph g) {

        marked = new boolean[g.v()];
        for (int i = 0; i < g.v(); i++) {
            if (!marked[i]) {
                dfs(g, i, i);
            }
        }
    }

    private void dfs(Graph g, int v, int u) {

        marked[v] = true;
        for (int w : g.adj(v)) {
            if (!marked[w]) {
                dfs(g, w, v);
            } else if (w != u) {
                hasCycle = true;
            }
        }
    }

    public boolean hasCycle() {
        return hasCycle;
    }
}
